package SortAlgorithm;

import com.alibaba.fastjson.JSON;

public class 冒泡排序 implements ISort{

    /**
     * 每次都从0开始遍历,将最大的数移动到最右边;
     */

    @Override
    public int[] sort(int[] arr) {
        return bubbleSort(arr);
    }

    //默认最坏情况
    public int[] bubbleSort(int[] arr){

        //大的排后面
        for (int i = 0; i < arr.length; i++) {
            //从下标0开始,遍历n次的(n-i-1)次
            for (int j = 0; j < arr.length-i-1; j++) {
                //保证当前j下标就是当前区域内的最大元素
                if(arr[j]>arr[j+1]){
                    swap(arr,j,j+1);
                }
            }
        }

        return arr;
    }

    //改进后的,最优情况,复杂度: N
    public int[] bubbleSortGood(int[] arr){

        //大的排后面
        for (int i = 0; i < arr.length; i++) {
            boolean flag=false;
            //从下标0开始,遍历n次的(n-i-1)次
            for (int j = 0; j < arr.length-i-1; j++) {
                //保证当前j下标就是当前区域内的最大元素
                if(arr[j]>arr[j+1]){
                    swap(arr,j,j+1);
                    flag=true;
                }
            }
            if(!flag){
                break;//说明没有发生交换,即arr[j]都是<arr[j+1],走过的路径都是有顺序的,直接break
            }
        }

        return arr;
    }

    private void swap(int[] arr,int index1,int index2){
        int temp=arr[index1];
        arr[index1]=arr[index2];
        arr[index2]=temp;
    }

    public static void main(String[] args) {
        冒泡排序 n=new 冒泡排序();
        int[] arr={5,1,2,4,9,6,3,7,8,0};
        int[] result = n.bubbleSort(arr);
        System.out.println(JSON.toJSONString(result));
    }
}
